package com.societyGames.utility
{
	public class BestStringHash
	{
		private var _keys:Vector.<String> = new Vector.<String>();
		private var _values:Vector.<Object> = new Vector.<Object>();
		
		public function BestStringHash()
		{	
		}
		
		public function setValue(key:String, value:Object):void
		{
			var index:int = findBestIndex(key);
			if (index == -1)//Insert at front.
			{
				this._keys.unshift(key);
				this._values.unshift(value);
			}
			else if (index == this._keys.length) //Insert at end.
			{
				this._keys.push(key);
				this._values.push(value);
			}
			else if (this._keys[index] == key) //replace
			{
				this._values[index] = value;	
			}
			else //insert after
			{
				this._keys.splice(index + 1, 0, key);
				this._values.splice(index + 1, 0, value);
			}
		}

		public function findBest(key:String):Object
		{
			var index:int = findBestIndex(key);
			if (index == -1) //No match
			{
			}
			else if (index != this._keys.length && key.search(this._keys[index]) == 0) //Equals a stored key.
			{
				return this._values[index];
			}
			else //Look one behind to see if what we're looking for starts with it.
			{	
				index--;
				if (index >= 0 && key.search(this._keys[index]) == 0)
				{
					return this._values[index]; 
				}	
			}
			return null;
		}

		//Find the key with the closest match or the exact match.
		//May return -1 as the best location.
		private function findBestIndex(key:String):int
		{
			var middle:int = -1;
			var first:int = 0;
			var last:int = this._keys.length - 1;
			while (first <= last)
			{
				//Find a middle value.
				middle = first + int((last - first) / 2);
				var middleKey:String = this._keys[middle];
				if (middleKey == key)
				{
					return middle;
				}
				else if (middleKey < key)
				{
					first = middle + 1;
					middle = first;
				}
				else
				{
					last = middle - 1;
					middle = last;
				}
			}
			return middle;
		}
	}
}

/*setValue("A", "A");
setValue("B", "B");
setValue("C", "C");

var value:Object;
value = findBest("A");
value = findBest("AB");
value = findBest("ABC");
value = findBest("B");
value = findBest("BC");
value = findBest("C");
value = findBest("CC");
value = findBest("D");
value = findBest("a");


this._keys.length = 0;
this._values.length = 0;

setValue("A", "A");
setValue("C", "C");
setValue("B", "B");

this._keys.length = 0;
this._values.length = 0;

setValue("B", "B");
setValue("A", "A");
setValue("C", "C");

this._keys.length = 0;
this._values.length = 0;

setValue("B", "B");
setValue("C", "C");
setValue("A", "A");

this._keys.length = 0;
this._values.length = 0;

setValue("C", "C");
setValue("A", "A");
setValue("B", "B");

this._keys.length = 0;
this._values.length = 0;

setValue("C", "C");
setValue("B", "B");
setValue("A", "A");

this._keys.length = 0;
this._values.length = 0;

var index:int;
index = findBestIndex("A");

this._keys.push("B");
index = findBestIndex("A");
index = findBestIndex("B");
index = findBestIndex("C");

this._keys.push("D");
index = findBestIndex("A");
index = findBestIndex("B");
index = findBestIndex("C");
index = findBestIndex("D");
index = findBestIndex("E");

this._keys.push("F");
index = findBestIndex("A");
index = findBestIndex("B");
index = findBestIndex("C");
index = findBestIndex("D");
index = findBestIndex("E");
index = findBestIndex("F");
index = findBestIndex("G");*/